1 package org.apache.lucene.codecs.memory;
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 import java.io.IOException;
21 import java.util.ArrayList;
22 import java.util.Arrays;
23 import java.util.BitSet;
24 import java.util.Collection;
25 import java.util.Collections;
26 import java.util.Iterator;
27 import java.util.List;
28 import java.util.TreeMap;
29
30 import org.apache.lucene.codecs.BlockTermState;
31 import org.apache.lucene.codecs.CodecUtil;
32 import org.apache.lucene.codecs.FieldsProducer;
33 import org.apache.lucene.codecs.PostingsReaderBase;
34 import org.apache.lucene.index.CorruptIndexException;
35 import org.apache.lucene.index.PostingsEnum;
36 import org.apache.lucene.index.FieldInfo;
37 import org.apache.lucene.index.FieldInfos;
38 import org.apache.lucene.index.IndexFileNames;
39 import org.apache.lucene.index.IndexOptions;
40 import org.apache.lucene.index.SegmentInfo;
41 import org.apache.lucene.index.SegmentReadState;
42 import org.apache.lucene.index.TermState;
43 import org.apache.lucene.index.Terms;
44 import org.apache.lucene.index.TermsEnum;
45 import org.apache.lucene.store.ByteArrayDataInput;
46 import org.apache.lucene.store.ChecksumIndexInput;
47 import org.apache.lucene.store.IndexInput;
48 import org.apache.lucene.util.Accountable;
49 import org.apache.lucene.util.Accountables;
50 import org.apache.lucene.util.ArrayUtil;
51 import org.apache.lucene.util.Bits;
52 import org.apache.lucene.util.BytesRef;
53 import org.apache.lucene.util.BytesRefBuilder;
54 import org.apache.lucene.util.IOUtils;
55 import org.apache.lucene.util.RamUsageEstimator;
56 import org.apache.lucene.util.automaton.ByteRunAutomaton;
57 import org.apache.lucene.util.automaton.CompiledAutomaton;
58 import org.apache.lucene.util.fst.BytesRefFSTEnum;
59 import org.apache.lucene.util.fst.BytesRefFSTEnum.InputOutput;
60 import org.apache.lucene.util.fst.FST;
61 import org.apache.lucene.util.fst.Outputs;
62 import org.apache.lucene.util.fst.PositiveIntOutputs;
63 import org.apache.lucene.util.fst.Util;
64
65
66
67
68
69
70
71
72
73
74 public class FSTOrdTermsReader extends FieldsProducer {
75 static final int INTERVAL = FSTOrdTermsWriter.SKIP_INTERVAL;
76 final TreeMap<String, TermsReader> fields = new TreeMap<>();
77 final PostingsReaderBase postingsReader;
78
79
80 public FSTOrdTermsReader(SegmentReadState state, PostingsReaderBase postingsReader) throws IOException {
81 final String termsIndexFileName = IndexFileNames.segmentFileName(state.segmentInfo.name, state.segmentSuffix, FSTOrdTermsWriter.TERMS_INDEX_EXTENSION);
82 final String termsBlockFileName = IndexFileNames.segmentFileName(state.segmentInfo.name, state.segmentSuffix, FSTOrdTermsWriter.TERMS_BLOCK_EXTENSION);
83
84 this.postingsReader = postingsReader;
85 ChecksumIndexInput indexIn = null;
86 IndexInput blockIn = null;
87 boolean success = false;
88 try {
89 indexIn = state.directory.openChecksumInput(termsIndexFileName, state.context);
90 blockIn = state.directory.openInput(termsBlockFileName, state.context);
91 int version = CodecUtil.checkIndexHeader(indexIn, FSTOrdTermsWriter.TERMS_INDEX_CODEC_NAME,
92 FSTOrdTermsWriter.VERSION_START,
93 FSTOrdTermsWriter.VERSION_CURRENT,
94 state.segmentInfo.getId(), state.segmentSuffix);
95 int version2 = CodecUtil.checkIndexHeader(blockIn, FSTOrdTermsWriter.TERMS_CODEC_NAME,
96 FSTOrdTermsWriter.VERSION_START,
97 FSTOrdTermsWriter.VERSION_CURRENT,
98 state.segmentInfo.getId(), state.segmentSuffix);
99
100 if (version != version2) {
101 throw new CorruptIndexException("Format versions mismatch: index=" + version + ", terms=" + version2, blockIn);
102 }
103
104 CodecUtil.checksumEntireFile(blockIn);
105
106 this.postingsReader.init(blockIn, state);
107 seekDir(blockIn);
108
109 final FieldInfos fieldInfos = state.fieldInfos;
110 final int numFields = blockIn.readVInt();
111 for (int i = 0; i < numFields; i++) {
112 FieldInfo fieldInfo = fieldInfos.fieldInfo(blockIn.readVInt());
113 boolean hasFreq = fieldInfo.getIndexOptions() != IndexOptions.DOCS;
114 long numTerms = blockIn.readVLong();
115 long sumTotalTermFreq = hasFreq ? blockIn.readVLong() : -1;
116 long sumDocFreq = blockIn.readVLong();
117 int docCount = blockIn.readVInt();
118 int longsSize = blockIn.readVInt();
119 FST<Long> index = new FST<>(indexIn, PositiveIntOutputs.getSingleton());
120
121 TermsReader current = new TermsReader(fieldInfo, blockIn, numTerms, sumTotalTermFreq, sumDocFreq, docCount, longsSize, index);
122 TermsReader previous = fields.put(fieldInfo.name, current);
123 checkFieldSummary(state.segmentInfo, indexIn, blockIn, current, previous);
124 }
125 CodecUtil.checkFooter(indexIn);
126 success = true;
127 } finally {
128 if (success) {
129 IOUtils.close(indexIn, blockIn);
130 } else {
131 IOUtils.closeWhileHandlingException(indexIn, blockIn);
132 }
133 }
134 }
135
136 private void seekDir(IndexInput in) throws IOException {
137 in.seek(in.length() - CodecUtil.footerLength() - 8);
138 in.seek(in.readLong());
139 }
140 private void checkFieldSummary(SegmentInfo info, IndexInput indexIn, IndexInput blockIn, TermsReader field, TermsReader previous) throws IOException {
141
142 if (field.docCount < 0 || field.docCount > info.maxDoc()) {
143 throw new CorruptIndexException("invalid docCount: " + field.docCount + " maxDoc: " + info.maxDoc() + " (blockIn=" + blockIn + ")", indexIn);
144 }
145
146 if (field.sumDocFreq < field.docCount) {
147 throw new CorruptIndexException("invalid sumDocFreq: " + field.sumDocFreq + " docCount: " + field.docCount + " (blockIn=" + blockIn + ")", indexIn);
148 }
149
150 if (field.sumTotalTermFreq != -1 && field.sumTotalTermFreq < field.sumDocFreq) {
151 throw new CorruptIndexException("invalid sumTotalTermFreq: " + field.sumTotalTermFreq + " sumDocFreq: " + field.sumDocFreq + " (blockIn=" + blockIn + ")", indexIn);
152 }
153 if (previous != null) {
154 throw new CorruptIndexException("duplicate fields: " + field.fieldInfo.name + " (blockIn=" + blockIn + ")", indexIn);
155 }
156 }
157
158 @Override
159 public Iterator<String> iterator() {
160 return Collections.unmodifiableSet(fields.keySet()).iterator();
161 }
162
163 @Override
164 public Terms terms(String field) throws IOException {
165 assert field != null;
166 return fields.get(field);
167 }
168
169 @Override
170 public int size() {
171 return fields.size();
172 }
173
174 @Override
175 public void close() throws IOException {
176 try {
177 IOUtils.close(postingsReader);
178 } finally {
179 fields.clear();
180 }
181 }
182
183 final class TermsReader extends Terms implements Accountable {
184 final FieldInfo fieldInfo;
185 final long numTerms;
186 final long sumTotalTermFreq;
187 final long sumDocFreq;
188 final int docCount;
189 final int longsSize;
190 final FST<Long> index;
191
192 final int numSkipInfo;
193 final long[] skipInfo;
194 final byte[] statsBlock;
195 final byte[] metaLongsBlock;
196 final byte[] metaBytesBlock;
197
198 TermsReader(FieldInfo fieldInfo, IndexInput blockIn, long numTerms, long sumTotalTermFreq, long sumDocFreq, int docCount, int longsSize, FST<Long> index) throws IOException {
199 this.fieldInfo = fieldInfo;
200 this.numTerms = numTerms;
201 this.sumTotalTermFreq = sumTotalTermFreq;
202 this.sumDocFreq = sumDocFreq;
203 this.docCount = docCount;
204 this.longsSize = longsSize;
205 this.index = index;
206
207 assert (numTerms & (~0xffffffffL)) == 0;
208 final int numBlocks = (int)(numTerms + INTERVAL - 1) / INTERVAL;
209 this.numSkipInfo = longsSize + 3;
210 this.skipInfo = new long[numBlocks * numSkipInfo];
211 this.statsBlock = new byte[(int)blockIn.readVLong()];
212 this.metaLongsBlock = new byte[(int)blockIn.readVLong()];
213 this.metaBytesBlock = new byte[(int)blockIn.readVLong()];
214
215 int last = 0, next = 0;
216 for (int i = 1; i < numBlocks; i++) {
217 next = numSkipInfo * i;
218 for (int j = 0; j < numSkipInfo; j++) {
219 skipInfo[next + j] = skipInfo[last + j] + blockIn.readVLong();
220 }
221 last = next;
222 }
223 blockIn.readBytes(statsBlock, 0, statsBlock.length);
224 blockIn.readBytes(metaLongsBlock, 0, metaLongsBlock.length);
225 blockIn.readBytes(metaBytesBlock, 0, metaBytesBlock.length);
226 }
227
228 public boolean hasFreqs() {
229 return fieldInfo.getIndexOptions().compareTo(IndexOptions.DOCS_AND_FREQS) >= 0;
230 }
231
232 @Override
233 public boolean hasOffsets() {
234 return fieldInfo.getIndexOptions().compareTo(IndexOptions.DOCS_AND_FREQS_AND_POSITIONS_AND_OFFSETS) >= 0;
235 }
236
237 @Override
238 public boolean hasPositions() {
239 return fieldInfo.getIndexOptions().compareTo(IndexOptions.DOCS_AND_FREQS_AND_POSITIONS) >= 0;
240 }
241
242 @Override
243 public boolean hasPayloads() {
244 return fieldInfo.hasPayloads();
245 }
246
247 @Override
248 public long size() {
249 return numTerms;
250 }
251
252 @Override
253 public long getSumTotalTermFreq() {
254 return sumTotalTermFreq;
255 }
256
257 @Override
258 public long getSumDocFreq() throws IOException {
259 return sumDocFreq;
260 }
261
262 @Override
263 public int getDocCount() throws IOException {
264 return docCount;
265 }
266
267 @Override
268 public TermsEnum iterator() throws IOException {
269 return new SegmentTermsEnum();
270 }
271
272 @Override
273 public TermsEnum intersect(CompiledAutomaton compiled, BytesRef startTerm) throws IOException {
274 return new IntersectTermsEnum(compiled, startTerm);
275 }
276
277 @Override
278 public long ramBytesUsed() {
279 long ramBytesUsed = 0;
280 if (index != null) {
281 ramBytesUsed += index.ramBytesUsed();
282 ramBytesUsed += RamUsageEstimator.sizeOf(metaBytesBlock);
283 ramBytesUsed += RamUsageEstimator.sizeOf(metaLongsBlock);
284 ramBytesUsed += RamUsageEstimator.sizeOf(skipInfo);
285 ramBytesUsed += RamUsageEstimator.sizeOf(statsBlock);
286 }
287 return ramBytesUsed;
288 }
289
290 @Override
291 public Collection<Accountable> getChildResources() {
292 if (index == null) {
293 return Collections.emptyList();
294 } else {
295 return Collections.singletonList(Accountables.namedAccountable("terms", index));
296 }
297 }
298
299 @Override
300 public String toString() {
301 return "FSTOrdTerms(terms=" + numTerms + ",postings=" + sumDocFreq + ",positions=" + sumTotalTermFreq + ",docs=" + docCount + ")";
302 }
303
304
305 abstract class BaseTermsEnum extends TermsEnum {
306
307
308 long ord;
309
310
311 final BlockTermState state;
312
313
314 final ByteArrayDataInput statsReader = new ByteArrayDataInput();
315 final ByteArrayDataInput metaLongsReader = new ByteArrayDataInput();
316 final ByteArrayDataInput metaBytesReader = new ByteArrayDataInput();
317
318
319 int statsBlockOrd;
320 int metaBlockOrd;
321
322
323 long[][] longs;
324 int[] bytesStart;
325 int[] bytesLength;
326
327
328 int[] docFreq;
329 long[] totalTermFreq;
330
331 BaseTermsEnum() throws IOException {
332 this.state = postingsReader.newTermState();
333 this.statsReader.reset(statsBlock);
334 this.metaLongsReader.reset(metaLongsBlock);
335 this.metaBytesReader.reset(metaBytesBlock);
336
337 this.longs = new long[INTERVAL][longsSize];
338 this.bytesStart = new int[INTERVAL];
339 this.bytesLength = new int[INTERVAL];
340 this.docFreq = new int[INTERVAL];
341 this.totalTermFreq = new long[INTERVAL];
342 this.statsBlockOrd = -1;
343 this.metaBlockOrd = -1;
344 if (!hasFreqs()) {
345 Arrays.fill(totalTermFreq, -1);
346 }
347 }
348
349
350 void decodeStats() throws IOException {
351 final int upto = (int)ord % INTERVAL;
352 final int oldBlockOrd = statsBlockOrd;
353 statsBlockOrd = (int)ord / INTERVAL;
354 if (oldBlockOrd != statsBlockOrd) {
355 refillStats();
356 }
357 state.docFreq = docFreq[upto];
358 state.totalTermFreq = totalTermFreq[upto];
359 }
360
361
362 void decodeMetaData() throws IOException {
363 final int upto = (int)ord % INTERVAL;
364 final int oldBlockOrd = metaBlockOrd;
365 metaBlockOrd = (int)ord / INTERVAL;
366 if (metaBlockOrd != oldBlockOrd) {
367 refillMetadata();
368 }
369 metaBytesReader.setPosition(bytesStart[upto]);
370 postingsReader.decodeTerm(longs[upto], metaBytesReader, fieldInfo, state, true);
371 }
372
373
374 final void refillStats() throws IOException {
375 final int offset = statsBlockOrd * numSkipInfo;
376 final int statsFP = (int)skipInfo[offset];
377 statsReader.setPosition(statsFP);
378 for (int i = 0; i < INTERVAL && !statsReader.eof(); i++) {
379 int code = statsReader.readVInt();
380 if (hasFreqs()) {
381 docFreq[i] = (code >>> 1);
382 if ((code & 1) == 1) {
383 totalTermFreq[i] = docFreq[i];
384 } else {
385 totalTermFreq[i] = docFreq[i] + statsReader.readVLong();
386 }
387 } else {
388 docFreq[i] = code;
389 }
390 }
391 }
392
393
394 final void refillMetadata() throws IOException {
395 final int offset = metaBlockOrd * numSkipInfo;
396 final int metaLongsFP = (int)skipInfo[offset + 1];
397 final int metaBytesFP = (int)skipInfo[offset + 2];
398 metaLongsReader.setPosition(metaLongsFP);
399 for (int j = 0; j < longsSize; j++) {
400 longs[0][j] = skipInfo[offset + 3 + j] + metaLongsReader.readVLong();
401 }
402 bytesStart[0] = metaBytesFP;
403 bytesLength[0] = (int)metaLongsReader.readVLong();
404 for (int i = 1; i < INTERVAL && !metaLongsReader.eof(); i++) {
405 for (int j = 0; j < longsSize; j++) {
406 longs[i][j] = longs[i-1][j] + metaLongsReader.readVLong();
407 }
408 bytesStart[i] = bytesStart[i-1] + bytesLength[i-1];
409 bytesLength[i] = (int)metaLongsReader.readVLong();
410 }
411 }
412
413 @Override
414 public TermState termState() throws IOException {
415 decodeMetaData();
416 return state.clone();
417 }
418
419 @Override
420 public int docFreq() throws IOException {
421 return state.docFreq;
422 }
423
424 @Override
425 public long totalTermFreq() throws IOException {
426 return state.totalTermFreq;
427 }
428
429 @Override
430 public PostingsEnum postings(PostingsEnum reuse, int flags) throws IOException {
431 decodeMetaData();
432 return postingsReader.postings(fieldInfo, state, reuse, flags);
433 }
434
435
436
437 @Override
438 public void seekExact(long ord) throws IOException {
439 throw new UnsupportedOperationException();
440 }
441
442 @Override
443 public long ord() {
444 throw new UnsupportedOperationException();
445 }
446 }
447
448
449 private final class SegmentTermsEnum extends BaseTermsEnum {
450 final BytesRefFSTEnum<Long> fstEnum;
451
452 BytesRef term;
453
454
455 boolean decoded;
456
457
458 boolean seekPending;
459
460 SegmentTermsEnum() throws IOException {
461 this.fstEnum = new BytesRefFSTEnum<>(index);
462 this.decoded = false;
463 this.seekPending = false;
464 }
465
466 @Override
467 public BytesRef term() throws IOException {
468 return term;
469 }
470
471 @Override
472 void decodeMetaData() throws IOException {
473 if (!decoded && !seekPending) {
474 super.decodeMetaData();
475 decoded = true;
476 }
477 }
478
479
480 void updateEnum(final InputOutput<Long> pair) throws IOException {
481 if (pair == null) {
482 term = null;
483 } else {
484 term = pair.input;
485 ord = pair.output;
486 decodeStats();
487 }
488 decoded = false;
489 seekPending = false;
490 }
491
492 @Override
493 public BytesRef next() throws IOException {
494 if (seekPending) {
495 seekPending = false;
496 SeekStatus status = seekCeil(term);
497 assert status == SeekStatus.FOUND;
498 }
499 updateEnum(fstEnum.next());
500 return term;
501 }
502
503 @Override
504 public boolean seekExact(BytesRef target) throws IOException {
505 updateEnum(fstEnum.seekExact(target));
506 return term != null;
507 }
508
509 @Override
510 public SeekStatus seekCeil(BytesRef target) throws IOException {
511 updateEnum(fstEnum.seekCeil(target));
512 if (term == null) {
513 return SeekStatus.END;
514 } else {
515 return term.equals(target) ? SeekStatus.FOUND : SeekStatus.NOT_FOUND;
516 }
517 }
518
519 @Override
520 public void seekExact(BytesRef target, TermState otherState) {
521 if (!target.equals(term)) {
522 state.copyFrom(otherState);
523 term = BytesRef.deepCopyOf(target);
524 seekPending = true;
525 }
526 }
527 }
528
529
530 private final class IntersectTermsEnum extends BaseTermsEnum {
531
532 BytesRefBuilder term;
533
534
535 boolean decoded;
536
537
538 boolean pending;
539
540
541
542
543
544 Frame[] stack;
545 int level;
546
547
548 final FST<Long> fst;
549 final FST.BytesReader fstReader;
550 final Outputs<Long> fstOutputs;
551
552
553 final ByteRunAutomaton fsa;
554
555 private final class Frame {
556
557 FST.Arc<Long> arc;
558
559
560 int state;
561
562 Frame() {
563 this.arc = new FST.Arc<>();
564 this.state = -1;
565 }
566
567 public String toString() {
568 return "arc=" + arc + " state=" + state;
569 }
570 }
571
572 IntersectTermsEnum(CompiledAutomaton compiled, BytesRef startTerm) throws IOException {
573
574 this.fst = index;
575 this.fstReader = fst.getBytesReader();
576 this.fstOutputs = index.outputs;
577 this.fsa = compiled.runAutomaton;
578 this.level = -1;
579 this.stack = new Frame[16];
580 for (int i = 0 ; i < stack.length; i++) {
581 this.stack[i] = new Frame();
582 }
583
584 Frame frame;
585 frame = loadVirtualFrame(newFrame());
586 this.level++;
587 frame = loadFirstFrame(newFrame());
588 pushFrame(frame);
589
590 this.decoded = false;
591 this.pending = false;
592
593 if (startTerm == null) {
594 pending = isAccept(topFrame());
595 } else {
596 doSeekCeil(startTerm);
597 pending = (term == null || !startTerm.equals(term.get())) && isValid(topFrame()) && isAccept(topFrame());
598 }
599 }
600
601 @Override
602 public BytesRef term() throws IOException {
603 return term == null ? null : term.get();
604 }
605
606 @Override
607 void decodeMetaData() throws IOException {
608 if (!decoded) {
609 super.decodeMetaData();
610 decoded = true;
611 }
612 }
613
614 @Override
615 void decodeStats() throws IOException {
616 final FST.Arc<Long> arc = topFrame().arc;
617 assert arc.nextFinalOutput == fstOutputs.getNoOutput();
618 ord = arc.output;
619 super.decodeStats();
620 }
621
622 @Override
623 public SeekStatus seekCeil(BytesRef target) throws IOException {
624 throw new UnsupportedOperationException();
625 }
626
627 @Override
628 public BytesRef next() throws IOException {
629
630 if (pending) {
631 pending = false;
632 decodeStats();
633 return term();
634 }
635 decoded = false;
636 DFS:
637 while (level > 0) {
638 Frame frame = newFrame();
639 if (loadExpandFrame(topFrame(), frame) != null) {
640 pushFrame(frame);
641 if (isAccept(frame)) {
642 break;
643 }
644 continue;
645 }
646 frame = popFrame();
647 while(level > 0) {
648 if (loadNextFrame(topFrame(), frame) != null) {
649 pushFrame(frame);
650 if (isAccept(frame)) {
651 break DFS;
652 }
653 continue DFS;
654 }
655 frame = popFrame();
656 }
657 return null;
658 }
659 decodeStats();
660 return term();
661 }
662
663 BytesRef doSeekCeil(BytesRef target) throws IOException {
664
665 Frame frame= null;
666 int label, upto = 0, limit = target.length;
667 while (upto < limit) {
668 frame = newFrame();
669 label = target.bytes[upto] & 0xff;
670 frame = loadCeilFrame(label, topFrame(), frame);
671 if (frame == null || frame.arc.label != label) {
672 break;
673 }
674 assert isValid(frame);
675 pushFrame(frame);
676 upto++;
677 }
678 if (upto == limit) {
679 return term();
680 }
681 if (frame != null) {
682 pushFrame(frame);
683 return isAccept(frame) ? term() : next();
684 }
685 while (level > 0) {
686 frame = popFrame();
687 while (level > 0 && !canRewind(frame)) {
688 frame = popFrame();
689 }
690 if (loadNextFrame(topFrame(), frame) != null) {
691 pushFrame(frame);
692 return isAccept(frame) ? term() : next();
693 }
694 }
695 return null;
696 }
697
698
699 Frame loadVirtualFrame(Frame frame) throws IOException {
700 frame.arc.output = fstOutputs.getNoOutput();
701 frame.arc.nextFinalOutput = fstOutputs.getNoOutput();
702 frame.state = -1;
703 return frame;
704 }
705
706
707 Frame loadFirstFrame(Frame frame) throws IOException {
708 frame.arc = fst.getFirstArc(frame.arc);
709 frame.state = fsa.getInitialState();
710 return frame;
711 }
712
713
714 Frame loadExpandFrame(Frame top, Frame frame) throws IOException {
715 if (!canGrow(top)) {
716 return null;
717 }
718 frame.arc = fst.readFirstRealTargetArc(top.arc.target, frame.arc, fstReader);
719 frame.state = fsa.step(top.state, frame.arc.label);
720
721 if (frame.state == -1) {
722 return loadNextFrame(top, frame);
723 }
724 return frame;
725 }
726
727
728 Frame loadNextFrame(Frame top, Frame frame) throws IOException {
729 if (!canRewind(frame)) {
730 return null;
731 }
732 while (!frame.arc.isLast()) {
733 frame.arc = fst.readNextRealArc(frame.arc, fstReader);
734 frame.state = fsa.step(top.state, frame.arc.label);
735 if (frame.state != -1) {
736 break;
737 }
738 }
739
740 if (frame.state == -1) {
741 return null;
742 }
743 return frame;
744 }
745
746
747
748 Frame loadCeilFrame(int label, Frame top, Frame frame) throws IOException {
749 FST.Arc<Long> arc = frame.arc;
750 arc = Util.readCeilArc(label, fst, top.arc, arc, fstReader);
751 if (arc == null) {
752 return null;
753 }
754 frame.state = fsa.step(top.state, arc.label);
755
756 if (frame.state == -1) {
757 return loadNextFrame(top, frame);
758 }
759 return frame;
760 }
761
762 boolean isAccept(Frame frame) {
763 return fsa.isAccept(frame.state) && frame.arc.isFinal();
764 }
765 boolean isValid(Frame frame) {
766 return frame.state != -1;
767 }
768 boolean canGrow(Frame frame) {
769 return frame.state != -1 && FST.targetHasArcs(frame.arc);
770 }
771 boolean canRewind(Frame frame) {
772 return !frame.arc.isLast();
773 }
774
775 void pushFrame(Frame frame) {
776 final FST.Arc<Long> arc = frame.arc;
777 arc.output = fstOutputs.add(topFrame().arc.output, arc.output);
778 term = grow(arc.label);
779 level++;
780 assert frame == stack[level];
781 }
782
783 Frame popFrame() {
784 term = shrink();
785 return stack[level--];
786 }
787
788 Frame newFrame() {
789 if (level+1 == stack.length) {
790 final Frame[] temp = new Frame[ArrayUtil.oversize(level+2, RamUsageEstimator.NUM_BYTES_OBJECT_REF)];
791 System.arraycopy(stack, 0, temp, 0, stack.length);
792 for (int i = stack.length; i < temp.length; i++) {
793 temp[i] = new Frame();
794 }
795 stack = temp;
796 }
797 return stack[level+1];
798 }
799
800 Frame topFrame() {
801 return stack[level];
802 }
803
804 BytesRefBuilder grow(int label) {
805 if (term == null) {
806 term = new BytesRefBuilder();
807 } else {
808 term.append((byte) label);
809 }
810 return term;
811 }
812
813 BytesRefBuilder shrink() {
814 if (term.length() == 0) {
815 term = null;
816 } else {
817 term.setLength(term.length() - 1);
818 }
819 return term;
820 }
821 }
822 }
823
824 static<T> void walk(FST<T> fst) throws IOException {
825 final ArrayList<FST.Arc<T>> queue = new ArrayList<>();
826 final BitSet seen = new BitSet();
827 final FST.BytesReader reader = fst.getBytesReader();
828 final FST.Arc<T> startArc = fst.getFirstArc(new FST.Arc<T>());
829 queue.add(startArc);
830 while (!queue.isEmpty()) {
831 final FST.Arc<T> arc = queue.remove(0);
832 final long node = arc.target;
833
834 if (FST.targetHasArcs(arc) && !seen.get((int) node)) {
835 seen.set((int) node);
836 fst.readFirstRealTargetArc(node, arc, reader);
837 while (true) {
838 queue.add(new FST.Arc<T>().copyFrom(arc));
839 if (arc.isLast()) {
840 break;
841 } else {
842 fst.readNextRealArc(arc, reader);
843 }
844 }
845 }
846 }
847 }
848
849 @Override
850 public long ramBytesUsed() {
851 long ramBytesUsed = postingsReader.ramBytesUsed();
852 for (TermsReader r : fields.values()) {
853 ramBytesUsed += r.ramBytesUsed();
854 }
855 return ramBytesUsed;
856 }
857
858 @Override
859 public Collection<Accountable> getChildResources() {
860 List<Accountable> resources = new ArrayList<>();
861 resources.addAll(Accountables.namedAccountables("field", fields));
862 resources.add(Accountables.namedAccountable("delegate", postingsReader));
863 return Collections.unmodifiableList(resources);
864 }
865
866 @Override
867 public String toString() {
868 return getClass().getSimpleName() + "(fields=" + fields.size() + ",delegate=" + postingsReader + ")";
869 }
870
871 @Override
872 public void checkIntegrity() throws IOException {
873 postingsReader.checkIntegrity();
874 }
875 }